#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>

typedef struct Node {
    char data;
    struct Node *next;
} Node;

bool detect_palindrome(Node *head, Node *left, Node **right)
{
    bool palindrome_exist = false;
    if (head != left)
    {
        palindrome_exist = detect_palindrome(head->next, left, right);
        if (palindrome_exist)
        {
            *right=(*right)->next;
            return detect_palindrome(head, head, right);
        }
        return palindrome_exist;
    }
    else
    {
        return (left->data == (*right)->data);
    }
}

bool has_palindrome(Node *head)
{
    //first: find left and right node pair in the middle 
    Node *slow = head;
    Node *fast = head;
    Node *left = NULL;
    Node *right = NULL;
    while (slow != NULL && fast != NULL && fast->next != NULL)
    {
        if (NULL == fast->next->next)
        {
            left = slow;
            right = left->next;
            break;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    if (fast->next == NULL)
    {
        left = slow;
        right = slow;
    }

    //second: detect palindrome from the middle to both sides
    return detect_palindrome(head, left, &right);
}

void print_list(Node * node)
{
    if (node != NULL)
    {
        printf("%c", node->data);
        if (node->next != NULL)
        {
            printf("->");
            print_list(node->next);
        }
        else
        {
            printf("\n");
        }
    }
}

Node *add_node(Node **list, Node *node)
{
    if (*list == NULL)
    {
        *list = node;
    }
    else
    {
        add_node(&(*list)->next, node);
    }
    return *list;
}

Node * new_node(char c)
{
    Node *node = calloc(1, sizeof(Node));
    node->data = c;
    return node;
}

Node * list_init_from_stdin(void)
{
    Node *list = NULL;
    int c = getchar();
    while (c != EOF)
    {
        if (isgraph(c))
        {
            add_node(&list, new_node(c));
        }
        c = getchar();
    }

    rewind(stdin);

    return list;
}

void release_list(Node *node)
{
    if (node == NULL)
    {
        return;
    }
    if (node->next != NULL)
    {
        release_list(node->next);
    }

    free(node);
}

int main(int argc, const char *argv[])
{
    printf("input some characters to init a list. ( EOF (ctr + z) on windows or (ctr + d) on *nix) to finish input)\n");

    Node *list = list_init_from_stdin();

    printf("\n");
    print_list(list);

    printf("\nthere is %spalindrome exist\n", has_palindrome(list)?"":"no ");

    release_list(list);

    return 0;
}
